Modern computers use virtual memory to-make the quantity of memory available for computation appear much greater than the actual physical memory within the computer. The physical memory, also known as main memory, is typically high-speed random access memory (RAM) in which currently active computer programs reside. Virtual memory is a memory management technique that allows all memory, including the physical memory and mass storage devices such as hard disks, to be addressed as one large address space. To permit this, the total memory is divided into blocks of data know as "pages" that are typically 512 or 1024 data words long, each word usually being one or more 8-bit bytes in length. The physical memory, because of its limited size, holds only a number of pages, with the rest of the pages being stored on the mass storage device. When the computer needs a data word, it generates a virtual address that contains a page number and a word number. The page number indicates which page of the virtual memory contains the desired data word, and the word number is the address of the word within the page. If a desired page resides in the physical memory, then the data word is immediately available. If a desired page does not, then the page containing the desired data is moved from the mass storage device into the physical memory. The process of moving pages between physical memory and mass storage is called "swapping" or "paging" and results in the replacement of a page in physical memory with a page from the mass storage device.
To determine whether a page resides in main memory, a device such as a translation-lookaside buffer (TLB) is used. The TLB contains a list of the pages currently in physical memory and their physical memory addresses. The TLB has two functions: to determine if a desired page is present in physical memory, and, if so, to translate the page's virtual address into a physical memory address. If the TLB determines the desired page is not present in the physical memory, then it signals that the page must be retrieved from the mass storage device.
TLBs may be designed in a number of ways, including with content-addressable memories (CAMs). A CAM is a memory device similar to a RAM, but with the ability to compare an incoming data word simultaneously to data stored at each address within the CAM and signal which address(es) match the incoming word. This is accomplished by placing a comparator in each memory location, or cell, within the CAM. The comparator compares the contents of its cell to a bit of the incoming data word. All comparator outputs along a CAM word are combined to form a sense line output. During a compare operation, a sense line stays active only if all cells along the word match the incoming data word, indicating a "hit." If any cells do not match, the sense line is forced inactive.
In a TLB, the CAM is typically paired with a RAM, with page numbers stored in the CAM and associated physical memory addresses stored in the RAM, An address translation consists of a compare operation in the CAM followed by a read cycle in the RAM. During the address translation, the incoming data word to the CAM is a page number that is simultaneously checked against all page numbers in the CAM. If a match is found, then the associated address in RAM is used as the physical page address, and the CAM signals a "hit" to the computer. The physical page address is then combined with the word number to provide the complete physical memory address for the data word. However, if no match is made, the CAM signals a "miss" and the computer responds by retrieving the page from mass storage.
Occasionally, a CAM will signal multiple hits, indicating the data word is at multiple locations in main memory. Multiple hits indicate an error, since the computer cannot determine which of the multiple hits is correct. If this error goes undetected, the computer may execute an incorrect instruction or use incorrect data, causing the final results to be in error or the program to abort. Sometimes this condition can be detected and the computer restarted, but many times it remains undetected. Consequently, techniques have been developed for detecting and differentiating between zero, one or multiple hits. If multiple hits are detected, the computer will be halted until appropriate steps are taken to minimize the damage.
One conventional approach for detecting multiple hits within a CAM is with multiple stages of digital combinational logic. The sense line outputs are divided into a number of small groups and each group is applied to a cell of logic gates that provide two outputs: a first signal that indicates one or more hits within the group, and a second signal that indicates multiple hits within that group. The first and second signals from all the cells are then applied to a second stage of similar cells, which reduces the number of signals while combining their collective information. This process continues until the last stage, a single cell, produces two output signals that indicate zero, one or multiple hits for the entire CAM. While accurate, this approach is inherently slow because of the delay inherent in the signals propagating through the vast amount of logic in the digital network.
A second conventional approach is analog in nature, with a faster speed of operation than the digital approach. It requires a detect line whose voltage falls at a rate proportional to the number of hits and a reference detect line whose voltage falls at a reference rate each time a compare occurs within the CAM. The voltage levels of the two detect lines are compared in an analog sense amplifier. If a single hit occurs, the voltage on the reference detect line falls at a faster rate than the voltage on the detect line and the sense amplifier does not signal a multiple hit. However, if multiple hits occur, the voltage on the detect line falls at a faster rate than the voltage on the reference detect line and the sense amplifier signals multiple hits. There are, however, several disadvantages of this approach. There is a risk associated with getting the timing correct on several critical signals to ensure that the detect lines are at the correct state when the sense amp is triggered. Also, the sense amplifier must have a sufficient voltage differential (including noise) on the inputs to operate correctly. Designs using this approach may need to be re-engineered to improve the timing or voltage differential, based on the results of a first attempt. Another problem is that the yield for integrated circuits using an analog design approach may be compromised if there are inaccuracies in the tracking of the critical signals over temperature, voltage and process.
An object of the invention, therefore, is to provide fast detection of single and multiple hits within a content-addressable memory or other device having multiple sense outputs that must be resolved. Another object is to provide such detection in a design that is free from the risks associated with the analog design. Yet another object of the invention is to provide such detection in a digital design that is predictable, reliable and easy to implement.